package leetcode;

import java.util.Arrays;

public class LeetCodeMain91 {
    public int num=0;
    public int findTargetSumWays(int[] nums, int target) {
        int length=nums.length;
        char[] chars=new char[length];
        Arrays.fill(chars,'+');
        int sum=0;
        for (int num:nums){
            sum+=num;
        }
        back(nums,chars,0,target,sum,Integer.MAX_VALUE);
        return count;
    }
    public void back(int[] nums,char[] chars,int startIndex,int target,int sum,int num){
        if (sum==target){
            count++;
            if (num==0){
                count++;
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            sum-=nums[i]*2;
            chars[i]='-';
            back(nums, chars, i+1, target, sum,nums[i]);
            sum+=nums[i]*2;
            chars[i]='+';
        }
    }

    public int count=0;
    public void Tree(TreeNode root){
        if (root==null){
            return;
        }
        Tree(root.right);
        root.val+=count;
        count=root.val;
        Tree(root.left);
    }
    public TreeNode convertBST(TreeNode root) {
        Tree(root);
        return root;
    }
    public static int findMaxGap(int[] A, int n) {
        // write code here
        int[] arr=new int[n];
        System.arraycopy(A,0,arr,0,n);
        Arrays.sort(arr);
        int max=arr[n-1];
        return Math.max(Math.abs(max-A[n-1]),Math.abs(A[0]-max));
    }

    public static void main(String[] args) {
        System.out.println(findMaxGap(new int[]{2,7,3,1,10,1},6));
    }
    public int[] clockwisePrint(int[][] mat, int n, int m) {
        if(mat == null || mat.length == 0 || mat[0].length == 0) {
            return new int[0];
        }
        int x = mat.length, y = mat[0].length, i = 0, j = 0, k = 0;
        int[] res = new int[x * y];
        while(i < x && j < y) {
            for (int t = j; t < y; t++) {
                res[k++]=mat[i][t];
            }
            i++;
            for (int t = i; t < x; t++) {
                res[k++]=mat[t][y-1];
            }
            y--;
            if (i>=x){
                break;
            }
            for (int t = y-1; t >= j; t--) {
                res[k++]=mat[x-1][t];
            }
            x--;
            if (j>=y){
                break;
            }
            for (int t = x-1; t >=i ; t--) {
                res[k++]=mat[t][j];
            }
            j++;
        }
        return res;
    }

    public int leastInterval(char[] tasks, int n) {
        int[] arr=new int[26];
        for (int i = 0; i < tasks.length; i++) {
            arr[tasks[i]-'A']++;
        }
        Arrays.sort(arr);
        int count=1;
        for (int i = 25; i > 0; i--) {
            if (arr[i]!=arr[i-1]){
                break;
            }
            count++;
        }
        return Math.max((arr[25] - 1) * (n + 1) + count , tasks.length);
    }
}
